1.Field of the Invention
This disclosure relates to coding methods and, in particular, to a Huffman decoder.
2.Description of the Related Art
Huffman coding is a variable length coding (VLC) technique for lossless data compression that, unlike the lossy nature of transform based coders, provides for the exact recovery of the original data from its compressed version. Compression is achieved by assigning longer codewords to less frequent input symbols and shorter codewords to the more frequent input symbols. Given the source symbol probability distribution, a Huffman coder achieves optimality; that is, the average length of Huffman code approaches the theoretical minimum, i.e., the entropy of the source, where the entropy of the source is defined as the minimum number of bits needed to encode the entire message with lossless compression.
Due to its simplicity and efficient compression capability, Huffman coding has been widely used in the international standards for Group 3 fax, Group 4 fax, JPEG image compression, and MPEG1/MPEG2 video compression.
Huffman encoders map the input source data into codewords of variable length, concatenate them all together and then segment them into fixed-length words (e.g., 8 bits or 16 bits). Huffman encoding can be implemented via table look-ups, or bit-serial operations by traversing a Huffman tree. The use of table look-ups usually speeds up the encoding process. A Huffman look-up table is built based on the empirical source symbol probability distribution. Due to the different characteristics of the data statistics, different applications may have different Huffman look-up tables.
Huffman decoding presents a set of unique challenges. Since different source symbols have different codeword lengths, the receiver has no knowledge of the boundaries of the consecutive codewords in a bitstream. The receiver usually has to decode the bitstream sequentially, bit-by-bit, by tracing a Huffman tree until a leaf (i.e., a terminating node) is reached. Tracing a Huff-man tree node-by-node is time-consuming. Table look-ups were proposed to speed up the decoding process. Traditional table look-ups allow receivers to decode one symbol at a time. However, it does not provide adequate throughput for very high data rate applications, such as decoding HDTV. See (Obed Duardo, et al. xe2x80x9cAn HDTV Video Decoder IC for A TV Receiversxe2x80x9d IEEE Transactions on Consumer Electronics. Vol. 43, number 3, pages 628-632, August, 1997 and S. F Chang and D. G. Messerschmitt. xe2x80x9cDesigning High-Throughput VLC Decoder Part Ixe2x80x94Concurrent VLSI Architectures.xe2x80x9d IEEE Transactions on Circuits and systems for Video Technology. Vol. 2, number 2, pages 187-196, June 1992). Given the proliferation of high data rate applications, the ability to decipher multiple-coded symbols in each clock cycle is desirable for clock speeds typically operated in the range of 15 to 100 Mhz.
Briefly and in general terms, in a preferred embodiment, the present invention provides a method to enhance the decoding rate of symbols from a coded bitstream. The coded bitstream includes one or more variable length codes (VLCs) produced by a Huffman code.
According to one aspect of the invention, an extended Huffman look-up table is constructed from an original Huffman look-up table wherein the extended Huffman look-up table contains row entries for decoding multiple variable length encoded symbols in a single clock cycle.
According to a second embodiment of the invention, a look-up table is constructed capable of decoding at least N Discrete Cosine Transform (DCT) coefficients in a single clock cycle so as to complete the decoding of an entire DCT block within 64/N+1 clock cycles.
The present invention advantageously improves the decoding rate (i.e., throughput) by extending an original Huffman table from the most frequent symbols while increasing the look-up table size a nominal amount.
A further advantage of the present invention, in accordance with the second embodiment, is that the decoding rate performance is guaranteed. This aspect is desirable from a hardware design perspective in that the method is adaptable to satisfy differing video hardware system requirements simply by adjusting the value of N (i.e., the number of coefficients to be decoded in a single cycle).